The present invention relates generally to decoders and, more specifically, to a turbo decoder that reduces processing time for the computation of A Posteroiri Probability (APP) and is suitable for implementation in parallel processing architectures.
Data delivered over a telecommunication channel are subject to channel noise, channel fading, and interferences from other channels. As a result, data received at the destination are usually “altered” by the channel from those delivered at the source. To ensure error-free transmission, the data are encoded before transmission by a channel encoder to allow the data receiver to detect or correct the errors. For example, if bit 0 is encoded as 000 and bit 1 is encoded as 111, then when one bit error occurs, 000 may become 100, and 111 may becomes 101. The receiver can correct 100 as 000 (bit 0) and 101 as 111 (bit 1) by the “majority rule” or the hamming distance. The part of receiver responsible for correcting errors is called a channel decoder.
Turbo encoders and decoders are used in emerging high-speed telecommunications transmission systems, such as terrestrial digital TV communication systems, and third generation wireless (e.g., WCDMA) communication systems. A turbo decoder has been demonstrated to approach the error correcting limit on both AWGN and Rayleigh fading channels.
Despite the error-correcting efficiency, however, a turbo decoder is computing intensive. To meet the real-time performance (e.g., a few millisecond), it is usually implemented in ASIC. If a turbo decoder is to be implemented in software running on a DSP or a CPU, as in the context of software defined radio, its real-time performance will be improved.
A 3GPP turbo encoder (FIG. 1) consists of a parallel concatenation of two identical RSC (Recursive Systematic Convolutional) encoders separated by an interleaver. The info word U of length K is encoded by the first RSC encoder, and the interleaved info word is encoded by the second RSC encoder. The interleaver de-correlates the inputs to the two RSC's by reordering the input bits to the second RSC, so that it is unlikely that the encoded bits from both RSC's have low weight code words at the same time. Also, it helps the encoded bits to cope with bursty noise. In 3GPP turbo encoder, a pseudo-random block interleaver is used. Both RSC encoded words are terminated by a trellis termination. The turbo encoded words are consists of systematic bits and two parity bits (U, Xp1, Xp2).
As shown in FIG. 2, the standard turbo decoder consists of two concatenated SISO (Soft Input Soft Output) blocks, one for each set of systematic and parity bits, (U′,Xp1′) and (U′,Xp2′), where Xp1′ and Xp2′ denote the noisy version of Xp1 and Xp2, respectively, and the same for U′ (U refers to the info words). The SISO blocks are A Posteriori Probability (APP) decoders also know as Maximum A Posteriori (MAP) decoders. The two SISO blocks are separated by the same interleaver (as the encoder) and its inverse block, the deinterleaver. Upon reception of bits from channel and priori information, each SISO block computes log posterior ratios of each bit with well-known forward and backward algorithm. Once SISO computes the log posterior ratios of all bits, it separates a probabilistic entity that was calculated based on its input from overall posterior, then pass it to the other SISO block. This probabilistic entity is often called extrinsic information (L12 and L21 in FIG. 2) for the other SISO block to use as prior information. The two SISO blocks run in an iterative scheme, mutually exchanging extrinsic information. After the required number of iterations is completed, hard decision is made based on accumulated soft information up to the iteration.
The log posterior probability ratio can be written as:
                                          L            ⁡                          (                              u                k                            )                                =                                    log              ⁡                              (                                                      P                    ⁡                                          (                                                                        u                          k                                                =                                                                              +                            1                                                    |                          y                                                                    )                                                                            P                    ⁡                                          (                                                                        u                          k                                                =                                                                              -                            1                                                    |                          y                                                                    )                                                                      )                                      =                          log              ⁡                              (                                                                            ∑                                              S                        +                                                              ⁢                                                                  P                        ⁡                                                  (                                                                                    S                                                              k                                -                                1                                                                                      ,                                                          S                              k                                                        ,                            y                                                    )                                                                    /                                              P                        ⁡                                                  (                          y                          )                                                                                                                                                ∑                                              S                        -                                                              ⁢                                                                  P                        ⁡                                                  (                                                                                    S                                                              k                                -                                1                                                                                      ,                                                          S                              k                                                        ,                            y                                                    )                                                                    /                                              P                        ⁡                                                  (                          y                          )                                                                                                                    )                                                    ,                            (        1        )            where S+ and S− denote the set of all possible state transitions caused by data input uk=+1 and uk=−1, respectively, and y denotes the set of observations, y=(y1, . . . , yk) where yk=(uk′, xk′), k=1, . . . , K. Note that yε(U′,Xp1′,Xp2′).
As usual, the posterior probability can be obtained by way of computing weighted likelihood, where weights are provided by the prior probability of the event uk. Direct evaluation of weighted likelihood requires the summations over a very large number of state patterns, which is proportional to the sequence length K. Because of the combinatorial complexity, it is not computationally feasible even for a reasonable length of the sequence.
To reduce the computation, an efficient procedure, known as forward and backward algorithm, is often used. In this algorithm, the posterior probability P(uk|y) is factorized into following 3 terms:                Forward variable, αk(.),        Backward variable, βk(.),        State transition probability, γk(.,.).        
The αk(.) is the joint probability of the observations y1, . . . , yk and the state at time k, that is αk(S)=P(Sk, y1, . . . , yk). The βk(.) represents the conditional probability of future observations given state at time k, βk(S)=P(y1, . . . , yK+1|Sk). The γk(.,.) is the probability of the state transitions from k−1 to k, caused by uk, and expressed as γk(S′, S)=P(Sk=S, yk|Sk−1=S′).
The procedure of recursive calculation of αk(S) is implemented according to
            α      k        ⁡          (      S      )        =            ∑              S        *              ⁢                            α                      k            -            1                          ⁡                  (                      s            ′                    )                    ⁢                                    γ            k                    ⁡                      (                                          S                ′                            ,              S                        )                          .            
For βk(S), the calculation is proceeded recursively as:
            β      k        ⁡          (      S      )        =            ∑              S        *              ⁢                            β                      k            +            1                          ⁡                  (                      S            ′                    )                    ⁢                                    γ                          k              +              1                                ⁡                      (                          S              ,                              S                ′                                      )                          .            
Since the turbo encoder is expected to start and end in state 1, the initial conditions for αk(.) and βk(.) are known and given as α0(S)=δ{S,1} and βK(S)=δ{S,1}, respectively, where δ{,.} denote the Kronecker delta.
Calculation of the posterior entity L(uk) as a function f(αk(.), βk(.)) is then equivalent to:
                              P          ⁡                      (                                          u                k                            |              y                        )                          =                                            ∑                              S                *                                      ⁢                                                            α                                      k                    -                    1                                                  ⁡                                  (                                      s                    ′                                    )                                            ⁢                                                γ                  k                                ⁡                                  (                                                            S                      ′                                        ,                    S                                    )                                            ⁢                                                β                  k                                ⁡                                  (                  S                  )                                                                          P            ⁡                          (              y              )                                                          (        2        )            where S* is the set of state pairs corresponding to all state transitions caused by uk=+1/−1, and P(y) is a normalization constant.
The procedure of forward and backward algorithm is summarized as:                Calculate γk(.,.), k=1,2, . . . , K;        Calculate αk(.,.) forward recursively, k=1,2, . . . , K;        Calculate βk(.,.) backward recursively, k=K−1, . . . 0;        Calculate (2) to form (1).        
The present invention is a method of decoding using a log posterior probability ratio L(uk), which is a function of forward variable α (.) and backward variable β (.). The method comprises dividing the forward variable α (.) and the backward variable β (.) into, for example, two segments p and q, where p plus q equal the length of the codeword U. The forward segments α (.) are parallel calculated, and the backward segments β (.) are parallel calculated. The ratio L(uk) is calculated using the parallel calculated segments of α (.) and β (.). The first forward segment is calculated from α1(.), . . . , αp(.) starting from α0(.), whereas the second forward segment is calculated from αp+1(.), . . . , αK(.) starting from an estimated αp(.). The first backward segment is calculated from βK−1(.), . . . , βq+1(.) starting from βK(.), and the second backward segment is calculated from βq(.), . . . , β1(.) starting from an estimated βq+1(.).
To obtain the estimated initial point α (.), the forward variable is calculated recursively from p−d+1 where d is an arbitrary amount of time and the state at time p−d+1 is treated as a uniform random variable. Similarly, for βq+1(.), the backward variable is calculated from q+d and again the state at time q+d is treated as a uniform random variable. With treating the states at time p−d+1 and q+d as uniform random variables, no informative prior knowledge of the states at the time is claimed.
The arbitrary amount of time, d, is in the range of 1 to 20 or may be in the range of 15 to 20. Also, the starting points for the estimated probability may also be a predetermined state. This predetermined state may be one divided by the number of possible states.
The method may include dividing the forward variable α (.) and the backward variable β (.) into more than two segments, and each of the forward and reverse segments would be calculated in parallel.
The process is performed in a signal receiver including a decoder.
These and other aspects of the present invention will become apparent from the following detailed description of the invention, when considered in conjunction with accompanying drawings.